As described in U.S. patent application Ser. No. 10/839,995, which is incorporated by reference herein, a low-density parity-check (LDPC) code is a linear block code specified by a parity-check matrix H. In general, an LDPC code is defined over a Galois Field GF(p), p≧2. If p=2, the code is a binary code. All linear block codes can be described as the product of a k-bit information vector s1×k with a code generator matrix Gk×n to produce an n-bit codeword x1×n where the code rate is r=k/n. The codeword x is transmitted through a noisy channel, and the received signal vector y is passed to the decoder to estimate the information vector s1×k.
Given an n-dimensional space, the rows of G span the k-dimensional codeword subspace C, and the rows of the parity-check matrix Hm×n span the m-dimensional dual space C⊥, where m=n−k. Since x=sG and GHT=0, it follows that xHT=0 for all codewords in subspace C, where “T” (or “T”) denotes matrix transpose. In the discussion of LDPC codes, this is generally written asHxT=0T,  (1)where 0 is a row vector of all zeros, and the codeword x=[s p]=[s0, s1, . . . , sk-1, p0, p1, . . . , pm-1], where p0, . . . , pm-1 are the parity-check bits; and s0, . . . , sk-1 are the systematic bits, equal to the information bits within the information vector.
For an LDPC code the density of non-zero entries in H is low, i.e., there are only a small percentage of 1's in H, allowing better error-correcting performance and simpler decoding than using a dense H. A parity-check matrix can be also described by a bipartite graph. The bipartite graph is not only a graphic description of the code but also a model for the decoder. In the bipartite graph, a codeword bit (therefore each column of H) is represented by a variable node on the left, and each parity-check equation (therefore each row of H) is represented by a check node on the right. Each variable node corresponds to a column of H and each check node corresponds to a row of H, with “variable node” and “column” of H referred to interchangeably, as are “check node” and “row” of H. The variable nodes are only connected to check nodes, and the check nodes are only connected to variable nodes. For a code with n codeword bits and m parity bits, variable node vi is connected to check node cj by an edge if codeword bit i participates in check equation j, i=0, 1, . . . , n−1, j=0, 1, . . . , m−1. In other words, variable node i is connected to check node j if entry hji of the parity-check matrix H is 1. Mirroring Equation (1), the variable nodes represent a valid codeword if all check nodes have even parity.
An example is shown below to illustrate the relationship between the parity-check matrix, the parity-check equations, and the bipartite graph. Let an n=12, rate- 1/2  code be defined by
                              H          =                                                                      [                                                                                    1                                                                    0                                                                    1                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                                                            0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                                                            0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                                                            1                                                                    0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                                                            0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                                                            0                                                                    0                                                                    0                                                                    1                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                    1                                                                              ]                                }                                            ︸                n                                      ⁢            m                          ,                            (        2        )            with the left side portion corresponding to k (=6) information bits s, the right side portion corresponding to m (=6) parity bits p. Applying (1), the H in (2) defines 6 parity-check equations as follows:
                    {                                                                                                ⁢                                                                                    x                        0                                            +                                              x                        2                                            +                                              x                        6                                            +                                              x                        7                                                              =                    0                                                                                                                                                                  x                      1                                        +                                          x                      4                                        +                                          x                      7                                        +                                          x                      8                                                        =                  0                                                                                                                                                x                      2                                        +                                          x                      5                                        +                                          x                      6                                        +                                          x                      8                                        +                                          x                      9                                                        =                  0                                                                                                                                                x                      0                                        +                                          x                      3                                        +                                          x                      9                                        +                                          x                      10                                                        =                  0                                                                                                                                                x                      1                                        +                                          x                      4                                        +                                          x                      10                                        +                                          x                      11                                                        =                  0                                                                                                                        ⁢                                                                                    x                        3                                            +                                              x                        5                                            +                                              x                        6                                            +                                              x                        11                                                              =                    0                                                                                .                                    (        3        )            H also has the corresponding bipartite graph shown in FIG. 1.
The general LDPC code described above may not be easy to implement in practice. Structures are often introduced into the parity-check matrix to allow fast encoding and decoding without sacrificing the error-correcting performance. A structured LDPC code design starts with a small mb×nb binary base matrix Hb, makes z copies of Hb, and interconnects the z copies to form a large m×n H matrix, where m=mb×z, n=nb×z. Using the matrix representation, to build an H from Hb each 1 in Hb is replaced by a z×z permutation submatrix, and each 0 in Hb is replaced by a z×z all-zero submatrix. The representation of the expansion of Hb is called the model matrix and is denoted by Hbm. Thus Hbm is simply a shorthand notation for H when z is known. This procedure essentially maps each edge of Hb to a vector edge of length z in H, each variable node of Hb to a vector variable node of length z in H, and each check node of Hb to a vector check node of length z in H. For a structured LDPC, the z×z submatrix may be a permutation matrix, a sum of permutation matrices, or any type of binary matrix. Since a permutation matrix P has a single 1 in each row and a single 1 in each column, the weight distribution of the expanded matrix H is the same as the base matrix Hb. Therefore, the weight distribution of Hb is chosen as close to the desired final weight distribution as possible. The permutation submatrices comprising H can be very simple without compromising performance, such as simple cyclic shifts and/or bit-reversals. In the case of cyclic shifts, Hbm can be written by replacing the 1's in Hb by non-negative integers that represent the shift sizes and replacing the 0's in Hb by −1.
In the transmitter, a vector s of k information bits is encoded based on H (or equivalently Hbm) to produce a vector x of n code bits, where k=n−m=z×kb, kb=(nb−mb). Vector x is sent through a noisy channel and a vector y of n contaminated signals are received. At the receiver, the LDPC decoder attempts to estimate s based on received vector y and the parity-check matrix H. To decode y and estimate the original information sequence s, an iterative decoding algorithm, such as belief propagation, is usually applied based on the bipartite graph. Soft information in the format of log-likelihood ratios (LLRs) of the codeword bits is passed between the bank of variable nodes and the bank of check nodes. The iteration is stopped either when all check equations are satisfied or a maximum allowed iteration limit is reached.
Structured LDPC codes may also be decoded with a layered decoder. A layered decoder typically has hardware to processes an entire vector row at one time. The layered decoder can potentially reduce the number of iterations required to achieve a given level of performance, thereby improving throughput.
In addition, the base matrix and assignment of permutation matrices for a given target parity check matrix H can be designed to provide an LDPC code that has good error-correcting performance and can be efficiently encoded and decoded. In U.S. patent application Ser. No. 10/839,995, a structured parity-check matrix H is described, wherein H is an expansion of a base matrix Hb and wherein Hb comprises a section Hb1 and a section Hb2, and wherein Hb2 comprises a first part comprising a column hb having an odd weight greater than 2, and a second part comprising matrix elements for row i, column j equal to 1 for i=j, 1 for i=j+1, and 0 elsewhere. The expansion of the base matrix Hb uses identical submatrices for 1's in each column of the second part H′b2, and the expansion uses paired submatrices for an even number of 1's in hb.
Although layered decoding can be used to potentially reduce the amount of processing and potentially increase throughput, a technique does not exist for designing Hb and assigning the permutation matrices for a given target H size which allows efficient encoding and layered decoding. Therefore, a need exists for building features into structured LDPC codes which can be encoded efficiently and high-speed layered decoded.